1. Field of the Invention
The invention relates to mixed-size design of integrated circuits and, in particular, to packing-based macro placement.
2. Description of the Related Art
Due to use of IP (intellectual property) modules and embedded memories, a modern VLSI chip often comprises a large number of macros. Mixed-size placement of both macros and standard cells has become more popular in different applications. As a result, many mixed-size placement algorithms are disclosed in different publications.
A first type of mixed-size placement algorithm places macros and standard cells simultaneously, which typically does not consider macro orientations and requires a robust macro legalizer to remove overlaps if macros/cells are not distributed evenly. A simulated annealing based multilevel placer mPG-MS, disclosed in Proceedings of ACM/IEEE Asia South Pacific Design Automation Conference by C.-C. Chang et. al in 2003, fixes macros level by level from large macros to small macros. A min-cut based pacer Feng Shui, disclosed in Proceedings of ACM International Symposium on Physical Design by A. Khatkhate et. al in 2004, considers standard cells and macros simultaneously using a fractional cut technique, which allows horizontal cut lines to not align with row boundaries. In addition, several analytical approaches have been proposed to accomplish mixed-size placement. APlace, disclosed in Proceedings of the IEEE/ACM International Conference on Computer-Aided Design by A. B. Kagng et. al in 2004, uses a bell-shaped potential function considering macro heights/widths based on non-linear programming to determine a global placement which evenly distributes macros/cells. mPL, disclosed in Proceedings of ACM International Symposium on Physical Design by T. Chan et. al in 2005, uses a generalized force-directed method for placement. UPlace, disclosed in Proceedings of ACM International Symposium on Physical Design by B. Yao et. al in 2005, uses quadratic programming and a discrete cosine transformation method to distribute macro/cells evenly, and a zone refinement technique for legalization is then applied.
A second type combines floorplanning and placement techniques. A min-cut floorplacer Capo, disclosed in Proceedings of the IEEE/ACM International Conference on Computer-Aided Design in 2004, is an example. The fixed-outline floorplanning is applied when necessary during min-cut placement to find allowable positions for macros. Embedded into a placement flow, floorplacement can consider macro orientations and find legal solutions more easily.
A third type separates the mixed-size placement into two stages, macro placement and standard-cell placement. Macro positions are determined before standard cells are placed into the rest area. A combinational technique is disclosed in ACM Transactions on Design Automation of Electronic Systems by S. N. Adya in 2005. A standard cell placer is used to obtain an initial placement. Standard cells are clustered as several soft macros based on the initial placement, and fixed-outline floorplanning is applied to find an overlap-free macro placement. Then, macros are fixed and standard cells replaced using a standard cell placer in the remaining space. Compared with the other types, the two-stage mixed-size placement is more robust since it guarantees a feasible solution as long as an overlap-free macro placement is obtained. Furthermore, macro orientations and placement constraints, such as pre-placed macros and placement blockages, can be easily handled.